package exam;

public class Test6 {
    public static void main(String[] args) {
        LIS(new int[]{1,6,4,7,5,3,2});
    }
    public static int LIS (int[] arr) {
        // write code here
        int n = arr.length;
        if(n == 0) return 0;
        int[] dp = new int[n + 1];
        for(int i = 0; i <= n; i++) dp[i] = 1;
        for(int i = 1; i <= n; i++) {
            for(int j = i - 1; j > 0; j--) {
                if(arr[i - 1] > arr[j - 1]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        return dp[n];
    }
}
